Multiplication of numbers represented in binary notation (powers of 2) is a common operation in digital circuits. Known in the art are a variety of techniques to perform multiplication. Some of these techniques employ a minimal amount of circuitry and consume relatively large amounts of time, while others operate quickly but require relatively extensive circuitry. A tradeoff between speed and circuit complexity is therefore mandated in the design of any electronic multiplier.
One approach commonly employed to speed up the operation of digital multiplier circuits is attributed to Booth and has the virtue of working properly on positive and negative, fractional and integer numbers represented in two's complement notation. A particular variant of Booth's method operates on two adjacent bit positions of the multiplier at every generation of an intermediate product. This variant provides a two-fold improvement in speed; first from the multiple shifts preceding generation of the intermediate product, and second from the two-bit look-ahead.
Circuitry which implements the Booth variant is known in the art but is, as mentioned, generally quite complex. While it is recognized in the art that certain of the least-significant bits of the intermediate products do not change after a certain point in the multiplication, and therefore, the resulting circuitry which implements the portion of the multiplier generating the least-significant bits of the product can be simplified, no equivalent savings are made in the portion implementing the most-significant bits of the product. This is due to the requirement to retain all of the most-significant bits of the intermediate product for subsequent inclusion in the sums forming later intermediate products.
Accordingly, there is a need for a multiplier having a circuit array which provides enough storage for each intermediate product without the redundant storage of bit positions for those most-significant bits which simply contain extraneous sign-extension information.